package com.hongyue.kuaiPai;

import java.util.ArrayList;
import java.util.Random;

public class Demo {
    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        ArrayList<Integer> a = new ArrayList<>();
        Random ra = new Random();
        for (int i = 0; i < 40; i++) {
            a.add(ra.nextInt(300) + 1);
        }
        System.out.println(a);
        ArrayList<Integer> b = KuaiPai(a);
        System.out.println(b);
        long i = System.currentTimeMillis();
        System.out.println("用时" + (i - l));
    }

    private static ArrayList<Integer> KuaiPai(ArrayList<Integer> arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        int zhong = arr.get(0);
        ArrayList<Integer> di = new ArrayList<>();
        ArrayList<Integer> gao = new ArrayList<>();
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) < zhong) {
                di.add(arr.get(i));
            } else if (arr.get(i) > zhong) {
                gao.add(arr.get(i));
            }
        }
        ArrayList<Integer> a = KuaiPai(di);
        ArrayList<Integer> b = KuaiPai(gao);
        a.add(zhong);
        a.addAll(b);
        return a;
    }
}
